METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)
Workshop on Expanders and derandomization (March 21-25, 2011)
Mar 23, 16:30-17:30 - Avi Wigderson (IAS Princeton)
Popular's talk at the École Normale Supérieure de Paris
The P vs. NP problem: Internet security, efficient computations and the limits of human knowledge
----
The P versus NP problem is a precise, easy to state mathematical problem.
Yet it stands unique in the philosophical meaning, and the impacts of its resolution.
If P equals NP, then we can hope to quickly answer most other mathematical and scientific challenges we face. If P does not equal NP, we can hope to make the security of electronic interactions unconditional.
In the talk I'll formulate the P versus NP problem, and explain these far reaching connections. I'll describe the research it has spun in Computational Complexity, and report on the attempts to resolve it.
